package com.zjsru.oneDay202212;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: CookLee
 * @Date: 2022/12/18
 *
 * 得到连续 K 个 1 的最少相邻交换次数
 *
 * 输入：nums = [1,0,0,1,0,1], k = 2
 * 输出：1
 * 解释：在第一次操作时，nums 可以变成 [1,0,0,0,1,1] 得到连续两个 1 。
 *
 * 输入：nums = [1,0,0,0,0,0,1,1], k = 3
 * 输出：5
 * 解释：通过 5 次操作，最左边的 1 可以移到右边直到 nums 变为 [0,0,0,0,0,1,1,1] 。
 *
 * 输入：nums = [1,1,0,1], k = 2
 * 输出：0
 * 解释：nums 已经有连续 2 个 1 了。
 */
public class MinMoves {
    
    public int minMoves(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        int z = 0;
        int i = 0;
        for (; i < nums.length; i++) {
            if (nums[i] == 1) {
                i++;
                break;
            }
        }
        //记录各个1之间0的个数，合并连续的0的集合
        for (; i < nums.length; i++) {
            if (nums[i] == 1) {
                list.add(z);
                z = 0;
            } else {
                z++;
            }
        }
        //按照滑动窗口的方式，计算对应的cost
        int cost = 0;
        // 把每个位置的cost乘上这个位置0的个数，也就是list[i]，再求和就得到窗口整体的cost。
        for (int j = 0; j < k - 1; j++) {
            cost += list.get(j) * Math.min(j + 1, k - j - 1);
        }
        int[] pre = new int[list.size() + 1];
        for (int j = 1; j <= list.size(); j++) {
            pre[j] += list.get(j - 1) + pre[j - 1];
        }
        int temp = cost;
        for (int j = k - 1; j < list.size(); j++) {
            //考虑奇偶的情况
            temp -= pre[k / 2 + (j - k + 1)] - pre[j - k + 1];
            temp += pre[j + 1] - pre[k / 2 + (j - k + 1) + k % 2];
            cost = Math.min(temp, cost);
        }
        return cost;
    }
    
    public static void main(String[] args) {
        MinMoves minMoves = new MinMoves();
        int[] nums = new int[] {1, 0, 0, 1, 0, 1};
        int k = 2;
        System.out.println(minMoves.minMoves(nums, k));
    }
}
